{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 快速排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### D&C练习\n",
    "\n",
    "#### E4.1 递归求和函数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-28T13:20:43.285637Z",
     "start_time": "2018-12-28T13:20:43.265172Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def sum_r(lst):\n",
    "    if lst == []:\n",
    "        return 0\n",
    "    else:\n",
    "        return lst[0] + sum_r(lst[1:])\n",
    "\n",
    "# test\n",
    "sum_r([1,2,3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-28T13:24:01.910002Z",
     "start_time": "2018-12-28T13:24:01.904478Z"
    }
   },
   "source": [
    "#### E4.2 递归求列表元素个数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-28T13:24:52.546834Z",
     "start_time": "2018-12-28T13:24:52.539380Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def count(lst):\n",
    "    if lst == []:\n",
    "        return 0\n",
    "    else:\n",
    "        return 1 + count(lst[1:])\n",
    "    \n",
    "# test\n",
    "count([1, 2, 3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### E4.3 递归求列表最大的数字\n",
    "\n",
    ">ps:感觉写的有些麻烦了？没有pattern matching不太会写了..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-28T13:29:45.760648Z",
     "start_time": "2018-12-28T13:29:45.743555Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def max_r(lst):\n",
    "    if lst == []:\n",
    "        return None\n",
    "    elif len(lst) == 1:\n",
    "        return lst[0]\n",
    "    elif len(lst) == 2:\n",
    "        return lst[0] if lst[0] > lst[1] else lst[1]\n",
    "    else:\n",
    "        return lst[0] if lst[0] > max_r(lst[1:]) else max_r(lst[1:])\n",
    "\n",
    "# test\n",
    "max_r([4,3,2,5,1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### E4.4 递归二分查找\n",
    "这个在第一章已经写过了。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-28T13:48:55.155707Z",
     "start_time": "2018-12-28T13:48:55.145801Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "def binarySearch(lst, value, low=0, high=-1):\n",
    "    if not lst:\n",
    "        return None\n",
    "    if high == -1:  # 保证只在首次调用时执行\n",
    "        high = len(lst)-1\n",
    "    if low >= high:\n",
    "        if lst[low] == value:\n",
    "            return low\n",
    "        else:\n",
    "            return None\n",
    "    mid = (low + high) // 2\n",
    "    if lst[mid] == value:\n",
    "        return mid\n",
    "    elif lst[mid] < value:\n",
    "        return binarySearch(lst, value, low=mid+1, high=high)\n",
    "    else:\n",
    "        return binarySearch(lst, value, low=0, high=mid-1)\n",
    "    \n",
    "# test\n",
    "print(binarySearch([1, 2, 3, 4, 5, 6], 2))\n",
    "print(binarySearch([1, 2, 3, 4, 5, 6], 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 快速排序\n",
    "\n",
    "- 特殊之处在于，快速排序的的速度取决于选择的基准值\n",
    "- 算法运行时间的最佳情况即为平均情况，此外还有最糟的情况\n",
    "- 算法运行时间为$O(nlogn)$ （平均情况）；最糟情况为$O(n^{2})$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-28T14:13:12.867617Z",
     "start_time": "2018-12-28T14:13:12.851819Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 5, 10]\n"
     ]
    }
   ],
   "source": [
    "def quickSort(array):\n",
    "    if len(array) < 2:\n",
    "        return array\n",
    "    else:\n",
    "        pivot = array[0]\n",
    "        less = [i for i in array[1:] if i <= pivot]\n",
    "        greater = [i for i in array[1:] if i > pivot]\n",
    "        return quickSort(less) + [pivot] + quickSort(greater)\n",
    "\n",
    "# test\n",
    "print(quickSort([10, 5, 2, 3]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2018-12-28T14:14:13.337720Z",
     "start_time": "2018-12-28T14:14:13.327523Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 5, 10]"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 皮一下，对三行快排的执着...\n",
    "def qsort(lst):\n",
    "    if len(lst) < 2: return lst\n",
    "    return qsort([v for v in lst[1:] if v <= lst[0]]) + [lst[0]] + qsort([v for v in lst[1:] if v > lst[0]])\n",
    "\n",
    "# test\n",
    "qsort([2, 3, 5, 10])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.7"
  },
  "toc": {
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "273px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
